The present invention relates generally to systems and methods for clock synchronization, and, more particularly, to a system and method for synchronizing clocks in packet networks which have variable or fixed length packets and that support variable synchronization intervals.
Communications networks, particularly wireless networks, typically employ a multiple-access protocol that is designed to prevent collisions of data packets due to simultaneous transmission of the data packets by multiple transmitters in the network using the same channel. One protocol that has come into widespread use is known as Time-Division Multiple Access (TDMA). In general, in accordance with the TDMA protocol, channel time is divided into small time slots, each of which is assigned to a different node (user). This time slot assignment can either be fixed (classical TDMA), or variable (reservation-based TDMA). In either case, since the number of nodes (users) is finite, the data is usually transmitted in TDMA xe2x80x9cframesxe2x80x9d, which ensure that the delays encountered by the different users are finite.
Clocks at two nodes in the network must be synchronized, up to a tolerance limit, to support the various network enabled operations such as the transmission of real time traffic, e.g., video data. Because clocks at different network nodes do not xe2x80x98tickxe2x80x99 at exactly the same frequency, the clocks tend to draft apart over time. The drift rate depends on how accurate (i.e., how expensive) the clocks are. Clocks commonly used in consumer devices and network equipment are rated in the neighborhood of 50-100 ppm (parts per million). That is, in the worst case, they can drift by as much as 1 millisecond in 10 seconds.
In a TDMA network, it is necessary that all transmitters and receivers in the network be synchronized in terms of the TDMA frame. An incorrectly synchronized transceiver, at best, cannot communicate, but, at worst, can cause the entire TDMA network to collapse if appropriate safeguards are not built into the protocol. It should be recognized that TDMA frame synchronization is not the same as clock synchronization of a modem, which is a function of the Physical layer (PHY). Usually, frame synchronization is achieved using a centralized control strategy implemented by a central controller (CC). However, frame synchronization can also be implemented in a distributed fashion.
In most TDMA networks, a universal time reference is required to properly allocate resources for transmission. This universal time reference is usually provided in the form of a xe2x80x9ctimestampxe2x80x9d, e.g., which specifies the current time. The timestamps are broadcast periodically by the central controller, and are used by the end terminals (WTs) to synchronize their xe2x80x9ctimestampxe2x80x9d registers.
For example, clock synchronization between two nodes connected via a direct wired or wireless link can be established as follows. A master clock copies its clock value, i.e., timestamp, in a packet and transmits that packet to a receiver at a predetermined interval. The receiver, upon receiving the packet compares the timestamp in the packet with its own timer value. If the values do not match, the time value at the receiver is adjusted accordingly.
There are, however, several shortcomings to, and limitations of, this approach. First, in order to work properly, this approach needs to know when the medium connecting the two nodes is free from other traffic. When the medium if free, the transmitter assembles the packet by computing data such as a CRC (cyclical redundancy code), FEC (forward error correction) and other header-type information. The transmitter also inserts the timestamp into the packet. These operations may take a variable amount of time depending on the packet size and other factors. This time variable may cause the transmission of the timestamp to be delayed.
Second, by the time the packet including the timestamp is assembled, the medium connecting the two nodes may become busy which would require discarding the assembled packet. The next disadvantage is that the layer with the time (i.e., the timer) needs to have direct access to the physical layer in order to find out if the medium connecting the two nodes is free or not. This information may not be available from different-types of physical layer implementations. In addition, the transmitter and receiver hardware need to deal with multiple real-time events in a short time frame such as checking the availability of the medium, inserting the timestamp in a packet, calculating the necessary header values, error checking and correction codes and transmitting the packet as soon as possible.
For example, in a reservation-based TDMA protocol, there are many problems with this timestamp-based approach. The reservation-based TDMA protocol has an interval during which the timestamp update must be sent. Otherwise, the timing jitter may be larger than what can be handled by a particular application, e.g., an MPEG decoder. The transmission of the timestamp value must also be reserved, and subsequently, other data must also be queued for transmission. In order to ensure efficient use of processor resources (which must be used for managing many other functions), this queuing is usually scheduled in advance. However, the timestamp value cannot be obtained until the exact time of transmission. Further, the queuing of the data packets behind the timestamp value cannot be done before the timestamp value is obtained. Of course, it is possible to switch the data stream between two separate queues with one holding the timestamp value and the other holding the data. However, this solution is quite complicated and requires precise synchronization.
A greater understanding of this problem can be gained by considering the case of a wireless asynchronous transfer mode (ATM) network that uses a reservation-based medium-access control (MAC) protocol. Broadband-ISDN, for example, typically uses ATM as the link layer of the network protocol. The MAC protocol implementation depends on a periodic control-data-frame (CDF). Each CDF contains many phases, during which both control and data information is sent from both the base station (BS) and the wireless terminal (WT). In this context, the BS corresponds to the previously described central controller (CC) and the WT corresponds to the previously described end terminal (WT).
The hardware design is based on the BS and each WT keeping the same timestamp values as a basis for computing the various phases of a CDF. All must maintain the same time periods in order to communicate and transfer packets effectively. All must synchronize their timestamps periodically, by copying the base station value, and all must take starting time directives from the BS.
The MAC processor is assumed to be interrupt-driven for both the WTs and the BS. The BS determines the timing for the entire system. Using the timestamp value as a reference, it determines the exact time when each of the phases operates. This timing information is sent during a certain phase. Since all phases are successive to each other, the WT and the BS set up a counter for the next phase based on the timing information, which then triggers an interrupt to the processor when the counter overflows. The processor must finish its functions during the respective phase within the time allotted and be prepared for the next phase.
For timestamp synchronization, the BS can be assumed to send a timestamp value during the certain phase. However, the BS may be busy storing packets intended for transmission during the certain phase. Consequently, the normal transmission stream must be stopped to allow for the timestamp value to be loaded from the timestamp register during the time of transmission. This solution is not desirable since it conflicts with the direct data path.
It should be appreciated that the problem described above is not due to the particular protocol considered, but is generally due to the reservation-based nature of the protocol, whereby decisions on what is transmitted at particular times are made in advance of those times.
In U.S. patent application Ser. No. 09/086,270, filed on May 28, 1998, the teachings of which are expressly incorporated herein, a two-step method was presented for synchronizing timestamps in a network (e.g., a wireless ATM network) that included a control node (BS) and a plurality of other nodes (WTs) which communicate with one another over a common channel mediated by a medium-access control (MAC) subsystem (e.g., one that uses a reservation-based TDMA protocol). Specifically, timestamp information is sent from the BS in two steps. First a command is sent to capture the current timestamp value (using a command timestamp_get). Then the captured timestamp value is sent at a later transmission (using a command timestamp_load), which is then used by the devices to adjust their timestamp value.
In U.S. patent application Ser. No. 09/217,470 filed on Dec. 21, 1998, the teachings of which are expressly incorporated herein, a one-step timestamp update method was presented to distribute the timestamp value among all transceivers in the network. Specifically, it combines the timestamp_get and timestamp_load commands in the two-step method described in the ""270 application into a single command, called the timestamp command. At the BS, when the timestamp command is sent from MAC to PHY over the MAC-PHY interface, the current timestamp value at the BS is captured from the MAC-PHY interface. Except at power-on, the timestamp value contained in the timestamp command and the captured timestamp value should be equal. The captured timestamp value is then added by a timestamp update interval, T, and stored to become the timestamp value included in the next timestamp transmission exactly T seconds later. The value of T can be varied at the BS as different physical conditions arise.
At each WT, when the timestamp command is received by PHY and sent to MAC over the MAC-PHY interface, the current timestamp value at the WT is captured from the MAC-PHY interface. The captured timestamp value is then compared with the timestamp value contained in the timestamp command and the difference, if any, is stored in an offset_register. This offset value will later be added to the timestamp counter in a non-time-critical manner under software control before the arrival of the next timestamp command.
Although the methods and systems discussed in the ""270 and ""470 applications provide significant flexibility in the design of software for the MAC protocol by allowing data and timestamp packets to be scheduled for transmission before the actual time of transmission, both of these approaches assume the context of a reservation-based and time division system (TDMA) under the control of a central controller (CC) or base station. The clocks are synchronized at fixed regular intervals. It is also assumed that there exists fixed cycles or packet sizes in the network.
There thus exists in the art a need for a clock synchronization method in packet networks that is not limited to synchronizing clocks at fixed regular intervals or the need for fixed cycles or packet sizes.
An object of the invention claim herein is to overcome the shortcomings and limitations of the methods and systems described above.
Other objects of the invention include to provide a simple a method for clock synchronization which can be employed in a variety of networks such as distributed (e.g., IEEE802.11) or centralized configurations, networks with fixed or variable packet sizes, and TDMA and non-TDMA based systems.
Another object of the invention is to provide a method that does not require information on whether the communication medium is availability is known or not.
Generally, various embodiments of the invention are directed to a synchronization approach that:
(a) can be employed to a variety of networksxe2x80x94wired as well as wireless, even with unpredictable packet processing delays at the MAC and PHY layers;
(b) can be simply and cheaply implemented with minimum real-time overhead (i.e., packet contents need not be processed in real-time);
(c) has minimum overhead in terms of the network capacity that is used; and
(d) supports flexible and variable synchronization intervals.
One aspect of the invention is related to a method for synchronizing clocks in a packet network that includes a master node and at least one slave node that communicate with one another. The method includes the step of retrieving a first timer value at the end of transmission of a current packet from the master node to the slave node. The current packet has an identifying code. The method also includes inserting the first timer value and the identifying code of the current packet into a subsequent packet to be sent to the slave node, upon receiving the current packet by the slave node, retrieving a second timer value from the slave node and associating the second timer value with the identifying code of the current packet. The method further includes transmitting the subsequent packet to the slave node, comparing the identifying code in the subsequent packet with the identifying code associated with the second timer value, calculating a difference between the first and second timer values if the identifying codes match, and adjusting a clock value in the slave node in accordance with the calculated difference.
Another aspect of the invention is related to a packet communication system including a master node including first controller and a first memory and at least one slave node including second controller and a second memory. The first processor is configured to execute the code stored in the first memory so as to retrieve a first timer value from a master clock at the end of transmission of a current packet to the slave node, the current packet having an identifying code, to assemble a subsequent packet, including the first timer value and the identifying code of the current packet, and to transmit the subsequent packet to the slave node. The second processor is configured to execute code stored in the second memory so as to retrieve a second timer value upon receiving the current packet from the master node, to associate the second timer value with the identifying code of the current packet, to receive and compare the identifying code in the subsequent packet with the identifying code associated with the second timer value, to calculate a difference between the first and second timer values if the identifying codes match, and to adjusts a clock value in the slave node in accordance with the calculated difference.
These and other aspects and embodiments of the present invention are exemplified in the following detailed disclosure.